// 验证搜索二叉树
// 测试链接 : https://leetcode.cn/problems/validate-binary-search-tree/
public class ValidateBinarySearchTree {
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
    }

    /*
    解题思路：利用先序遍历 要求节点符合 左 <  中 < 右
     */

    public static TreeNode[] stack = new TreeNode[10001];
    public static int top;

    public boolean isValidBST(TreeNode root) {
        if(root == null){  //特殊情况
            return true;
        }
        TreeNode pre = null;  //记录先序遍历的前一个
        top = 0; //清空栈
        while (root != null || top != 0){
            if(root != null){
                stack[top++] = root;
                root = root.left;
            }else{
                TreeNode cur = stack[--top];
                if(pre != null && pre.val > cur.val){
                    return false;
                }
                root = cur.right;
                pre = cur;
            }
        }
        return true;
    }


    /*
    解题思路：要求每一棵的子树都符合，左子树的最大值 < 当前节点的值 < 右子树的最小值
     */

    public static long max,min;
    public boolean isValidBST2(TreeNode root) {
        if(root == null){
            min = Long.MAX_VALUE;
            max = Long.MIN_VALUE;
            return true;
        }
        boolean leftBalance = isValidBST2(root.left);  //验证左子树是否平衡，并且刷新左子树的最大值和最小值
        long lmin = min;
        long lmax = max;
        boolean rightBalance = isValidBST2(root.right); //验证右子树是否平衡，并且刷新右子树的最大值和最小值
        long rmin = min;
        long rmax = max;

        min = Math.min(Math.min(lmin,rmin), root.val);
        max = Math.max(Math.max(lmax,rmax), root.val);

        return leftBalance && rightBalance && min < root.val && root.val < max;
    }
}
